package dp;

import java.util.Scanner;

//数位Dp，用于解决[left, right] 中满足条件L的所有数的个数(或和、积)
public class DigitDp {

	/**
	 * 
	 // 仔细考虑，显然[L,R]中满足条件的个数，等于[0,R]减去[0,L - 1]满足条件的个数， //
	 * 这样我们第一步把问题变成了求f(n)的问题，其中f(n)表示区间[0,n]内满足条件Q的个数。
	 * 
	 * // 因此我们需要一个二维数组dp[len][digit]， 表示长度为len位(可以有前导0)， //
	 * 且最高位为digit的且满足条件Q的数字的个数。而如何求dp[i][j]? 注意到当最高位固定为j时， //
	 * 我们只需要根据需要枚举下一位，即第i-1位，此时只需要从0枚举到9(假设问题都是10进制)即可。 
	 * // 最后我们再根据这些dp的结果，求出n即可
	 * 
	 * // 但是上面的方法还是稍微复杂，因为需要先求出dp数组，然后还要枚举n的各位情况。但是我们通过对代码的修改， 
	 * // 可以将其合并在一起。事实上我们需要三个东西：
	 * 
	 * // 1. DP[len][digit]数组，用来记录中间数据，定义为上面的定义 
	 * // 2. solve(n) 用来求出[0,n]中满足条件Q的整数的个数(或者和、积等)， 
	 * //主要分两步：第一步求出n的长度len并将n的各个数位存在全局数组bits中，第二步调用下面的dfs(l+1, 0, true)用来求结果 
	 * //3. dfs(len, digit, end_flag)结合bits和dp两个数组，求出结果， 
	 * 
	 * //并有可能将结果存入对应dp数组中以免多次计算同一种情况(记忆化搜索)
	 * 
	 * // 这个函数前两个参数很容易理解，关键是最后一个end_flag， 事实上由于我们把求dp数组和 
	 * // 求[0,n]中满足Q的整数个数这两个步骤合在了一起，因此dfs必须区分这两种情况，而区分的方法就是用end_flag做标记：
	 * 
	 * // 当该标记为true的时候，表示前面枚举的高位和n的高位完全相同，因此这一步枚举下一位时，为了使数字大小不超过n，
	 * // 必须只能枚举到bits[低位]，并且计算的结果不能存入dp数组
	 * 
	 * // 反之，如果为false,表示之前枚举的高位已经小于n对应高位了，那么这一步在枚举下一位时，可以从0枚举到9， 
	 * // 且计算结果可以存入dp数组
	 * 
	 * //这里考虑的是求个数，模板代码
	 */

	private int[][] dp;

	int[] bitsTemp = new int[10];

	//flag标记是否当前位是否等于n的该位
	public int dfs(int length, int digit, boolean flag) {
		if (length <= 0) {
			return 0;
		}
		if (!flag && dp[length][digit] != -1) {
			return dp[length][digit];
		}
		//如果只有1位，我们判断是否满足条件
		if (length == 1) {
			// 如果满足条件Q，那么返回1, 如果不满足条件，返回0
			// return (Q? 1 : 0);
		}
		// 开始枚举下一位的数字
		// flag是否当前位是否等于n的该位
		// bits[len - 2]是满足条件的下一位数字
		//如果flag为true，表示之前的已经相等，所以不能枚举到9，只能枚举到该位的数字
		//为什么是length - 2呢,因为我们数组下标为0的存储着第一个数字
		//所以下标为length - 2的存储着第length - 1位的数字
		int end = flag ? bitsTemp[length - 2] : 9;
		int ans = 0;
		for (int j = 0; j <= end; j++) {
			ans += dfs(length - 1, j, flag && j == end);
		}
		//只有flag为false,我们才更新dp数组
		if (!flag) {
			dp[length][digit] = ans;
		}
		return ans;
	}

	public int solve(int n) {
		if (n <= 0) {
			return 0;
		}
		// 求出n的位数，并将其每一位存入数组bits中
		int length = 0;
		for (int i = 0; i < bitsTemp.length; i++) {
			bitsTemp[i] = 0;
		}
		//数组中的低位存储着数字的低位
		while (n != 0) {
			//如果这里改成bitsTemp[++length] = n % 10
			//那么dfs中的就要相应的改成end = flag ? bitsTemp[length - 1] : 9;
			bitsTemp[length++] = n % 10;
			n /= 10;
		}
		// 调用dfs求出最后结果，注意到第一个参数length + 1是指我们将n前补一个高位0，然后开始查找，
		// 这样避免了枚举原来n的最高位
		return dfs(length + 1, 0, true);
	}

	
	
	
	// hihocoder 交错和
	private static final int MOD = 1000000000 + 7;

	class Node {
		long sum, count = -1; // sum代表和，count代表个数
	}

	//digitDp[i][j][k]表示i位最低位为j时和为k的Node
	private Node[][][] digitDp = new Node[20][20][400];
	private long[] base = new long[20];
	private int[] bits = new int[20];

	
	
	// length数位长度, digit是首个数字, beginZero表示是否前面全部都是0
	// flag表示下一位枚举时是否枚举到bit[length - 2]，否则就枚举到9， sum是要求的数字和
	public Node dfs(int length, int digit, boolean beginZero, boolean flag, int sum) {
		Node res = new Node();
		res.sum = 0;
		res.count = 0;
		// 超过边界值
		if (length < -1 || length >= 20 || digit < 0 || digit > 9 || sum < -100
				|| sum > 100) {
			return res;
		}
		if (length == -1) {
			if (digit != sum) {
				return res;
			}
			res.count = 1;
			res.sum = sum;
			return res;
		}
		
		// 返回已有的DP结果，即记忆化搜索
		if (!flag && digitDp[length][digit + (beginZero ? 0 : 10)][sum + 100].count != -1) {
			return digitDp[length][digit + (beginZero ? 0 : 10)][sum + 100];
		}
		// 开始枚举下一位的数字
		int end = flag ? bits[length] : 9;
		//期望的newSum
		int newsum = digit - sum;
		Node temp;
		for (int j = 0; j <= end; j++) {
			//不是很理解这里的beginZero的思想
			//大致上是如果为0就没有变号，如果该位为1....end，就是变号的
			//但是不知道这是用来干嘛的
			if (!beginZero) {
				temp = dfs(length - 1, j, j != 0, flag && (j == end), sum);
			} else {
				temp = dfs(length - 1, j, true, flag && (j == end), newsum);
			}
			// System.out.println("temp: sum" + temp.sum + " res Sum: " + res.sum);
			res.count += temp.count;
			
			res.sum = ((res.sum + temp.sum) % MOD + ((temp.count * digit) % MOD * base[length + 1]) % MOD) % MOD;
		}
		if(!flag){
			digitDp[length][digit + (beginZero ? 0 : 10)][sum + 100] = res;
		}
		return res;
	}
	
	
	//感觉正确的写法应该是这样的
	//理解了
	public Node dfs2(int length, int digit, boolean beginZero, boolean flag, int sum) {
		//存放长度为 len的结果
		Node res = new Node();
		res.sum = 0;
		res.count = 0;
		// System.out.println("length: " + length + " sum:" + sum);
		// 超过边界值
		if (length < -1 || length >= 20 || digit < 0 || digit > 9 || sum < -100
				|| sum > 100) {
			return res;
		}
		if (length == -1) {
			if (digit != sum) {
				return res;
			}
			res.count = 1;
			res.sum = sum;
			return res;
		}
		
		// 返回已有的DP结果，即记忆化搜索
		if (!flag && digitDp[length][digit + (beginZero ? 0 : 10)][sum + 100].count != -1) {
			return digitDp[length][digit + (beginZero ? 0 : 10)][sum + 100];
		}
		// 开始枚举下一位的数字
		int end = flag ? bits[length] : 9;
		//期望的newSum
		//总算是看懂这一步了
		//newSum是这样计算的
		//a1是最高位，a2是次高位
		// ... a4 - (a3 - (a2 - (a1 - sum)))
		//如果到了最后一位a4 - (a3 - (a2 - (a1 - sum))) = a5
		//那么化简得a1 - a2 + a3 - a4 + a5 = sum
		int newsum = digit - sum;
		Node temp;
		for (int j = 0; j <= end; j++) {
			//如果明白了newSum的意思，我们为什么不直接传递newSum呢
			//因为我们首先传递的是最高位的前一位，所以我们不能直接传递newSum
			//Okay, 那我们设一个变量start表示是最开始，行不
			//同样不行，这里的关键就是如果我们这样做就默认着所有的数都是有length位的
			//你可能说不是length位也没关系啊，前面的0 - 0 - 0 -...(0 - sum)又没有影响
			//错了，有影响的，因为可能是-sum,比如00091 和为8(0 - 0 + 0 - 9 + 1 = -8)
			//看出来了没，这就是我们需要beginZero的原因,到应该加的才开始加
			
//			if (start) {
//				temp = dfs2(length - 1, j, false, flag && (j == end), sum);
//			} else {
//				temp = dfs2(length - 1, j, false, flag && (j == end), newsum);
//			}
			
			//如果前面都是0，并且当前 j也为0
			if (beginZero) {
				temp = dfs2(length - 1, j, j == 0, flag && (j == end), sum);
			} else {
				temp = dfs2(length - 1, j, false, flag && (j == end), newsum);
			}
			// 满足条件的个数
			res.count += temp.count;
			// 每一个： data[len] = digit * base[len] + data[len - 1]  且共有n个
			// res.sum = res.sum + temp.count * (digit * base[len]) + temp.sum 增加 %mod 就得到下面的结果
			res.sum = ((res.sum + temp.sum) % MOD + ((temp.count * digit) % MOD * base[length + 1]) % MOD) % MOD;
		}
		if(!flag){
			//这儿为什么要进行区分呢
			//因为beginZero的长度其实不是这么length长的(不算前导0)，所以需要添加
			digitDp[length][digit + (beginZero ? 0 : 10)][sum + 100] = res;
		}
		return res;
	}
	
	long count = 0;
	
	//sign为true表示正号，sign为false表示负号
	//看起来这样写是O(10^length),我感觉这个效率不高，还是预处理那样好吧
	//TODO 还不正确
	public Node dfsSum(int length, int digit, boolean flag, boolean sign, int sum) {
		Node res = new Node();
		res.sum = 0;
		res.count = 0;
		count++;
		// System.out.println("cur length " + length);
		// 超过边界值
		if (length < -1 || length >= 20 || digit < 0 || digit > 9 || sum < -100
				|| sum > 100) {
			return res;
		}
		
		//同样，面临4 与0004(0 - 0 + 0 - 4)这种情况
		//感觉这样不好，该方法不通
		if (length == -1) {
			if ( (sign && digit != sum) || (!sign && digit != -sum)) {
				return res;
			}
			res.count = 1;
			res.sum = digit;
			return res;
		}
		
		// 返回已有的DP结果，即记忆化搜索
		if (!flag && digitDp[length][digit][sum + 100].count != -1) {
			return digitDp[length][digit][sum + 100];
		}
		// 开始枚举下一位的数字
		int end = flag ? bits[length] : 9;
		//期望的newSum
		Node temp;
		for (int j = 0; j <= end; j++) {
			//sign为true表示正号
			if (sign) {
				// System.out.println(" cur is minus");
				temp = dfsSum(length - 1, j, flag && (j == end), !sign, sum - digit);
			} else {
				// System.out.println(" cur is positive");
				temp = dfsSum(length - 1, j, flag && (j == end), !sign, sum + digit);
			}
			// System.out.println("temp: sum" + temp.sum + " res Sum: " + res.sum);
			res.count += temp.count;
			res.sum = ((res.sum + temp.sum) % MOD + ((temp.count * j) % MOD * base[length]) % MOD) % MOD;
		}
		if(!flag){
			digitDp[length][digit][sum + 100] = res;
		}
		return res;
	}

	public int solve(long n, int sum) {
		if (n <= 0) {
			return 0;
		}
		int length = 0;
		for (int i = 0; i < bits.length; i++) {
			bits[i] = 0;
		}
		while (n != 0) {
			bits[length++] = (int) (n % 10);
			n /= 10;
		}
//		return (int) dfs(length - 1, 0, false, true, sum).sum;
//		return (int) dfs2(length - 1, 0, true, true, sum).sum;
		System.out.println("length " + length);
		return (int) dfsSum(length - 1, 0, true, false, sum).sum;
	}

	public static void main(String[] args) {
		DigitDp object = new DigitDp();
		object.getRes();
	}

	public void getRes(){
		Scanner scanner = new Scanner(System.in);
		long left, right;
		int sum;
		Node temp = new Node();
		//初始化
		for (int i = 0; i < 20; i++) {
			for (int j = 0; j < 20; j++) {
				for (int k = 0; k < 201; k++) {
					digitDp[i][j][k] = temp;
				}
			}
		}
		base[0] = 1;
		for(int i = 1; i < base.length; i++){
			base[i] = (base[i - 1] * 10) % MOD;  
		}
		while(scanner.hasNext()){
			left = scanner.nextLong();
			right = scanner.nextLong();
			sum = scanner.nextInt();
			System.out.println((solve(right, sum) - solve(left - 1, sum) + MOD) % MOD); 
//			int rightRes = solve(right, sum);
//			int leftRes = solve(left - 1, sum);
//			System.out.println(" rightRes: " + rightRes + "  leftRes " + leftRes);
//			System.out.println("count: " + count);
//			System.out.println(rightRes - leftRes);
		}
		scanner.close();
	}
}
